#include "include/pf_list.h"
#include "include/pf_internal.h"

#include <stdio.h>
#include <stdlib.h>

struct pf_list_node
{
    void* data;
    struct pf_list_node* prev;
    struct pf_list_node* next;
};

struct pf_list
{
    struct pf_list_node* head;
    struct pf_list_node* tail;
    uint32_t size;
};

/*********************************************************************************************
Function Name:  pf_list_sort_merge
Description  :  
Inputs       :  pf_list_t* list                                : The list pointer
                pf_list_node_t* l1                             :
                pf_list_node_t* l2                             :
                int (*compare_func)(const void*, const void*)  :
Outputs      :
ErrorCodes   :
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-23                    create
**********************************************************************************************/
static inline pf_list_node_t* pf_list_sort_merge(pf_list_t* list,
                                                 pf_list_node_t* l1,
                                                 pf_list_node_t* l2,
                                                 int (*compare_func)(const void*, const void*));

/*********************************************************************************************
Function Name:  pf_list_sort_mine
Description  :  
Inputs       :  pf_list_t* list                                : The list pointer
                pf_list_node_t* list_node                      :
                int (*comp)(const void*, const void*)          :
Outputs      :
ErrorCodes   :
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-23                    create
**********************************************************************************************/
static inline pf_list_node_t* pf_list_sort_mine(pf_list_t* list,
                                                pf_list_node_t* list_node,
                                                int (*comp)(const void*, const void*));

/*********************************************************************************************
Function Name:  pf_list_partion
Description  :  
Inputs       :  pf_list_node_t* node_low                       : 
                pf_list_node_t* node_high                      :
                int (*comp)(const void*, const void*)          :
Outputs      :
ErrorCodes   :
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-23                    create
**********************************************************************************************/
static inline pf_list_node_t* pf_list_partion(pf_list_node_t* node_low, 
                                              pf_list_node_t* node_high,
                                              int (*comp)(const void*, const void*));

/*********************************************************************************************
Function Name:  pf_list_quick_sort
Description  :  
Inputs       :  pf_list_node_t* node_low                       : 
                pf_list_node_t* node_high                      :
                int (*comp)(const void*, const void*)          :
Outputs      :
ErrorCodes   :
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-23                    create
**********************************************************************************************/
static inline void pf_list_quick_sort(pf_list_node_t* node_low, 
                                      pf_list_node_t* node_high,
                                      int (*comp)(const void*, const void*));

/********************************************************************************************/

pf_list_t* pf_list_create(void)
{
    pf_list_t* list = malloc(sizeof(pf_list_t));

    if(!list)
    {
        pf_set_errno(PF_ENOMEM);
        return NULL;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;

    return list;
}

int pf_list_destory(pf_list_t* list)
{
    assert(list);

    pf_list_clear(list);
    free(list);

    return 0;
}

void* pf_list_get_value(const pf_list_node_t* node)
{
    assert(node);

    return node->data;
}

pf_list_node_t* pf_list_head(const pf_list_t* list)
{
    assert(list);

    return list->head;
}

pf_list_node_t* pf_list_tail(const pf_list_t* list)
{
    assert(list);

    return list->tail;
}

pf_list_node_t* pf_list_next(const pf_list_node_t* cur_node)
{
    assert(cur_node);

    return cur_node->next;
}

pf_list_node_t* pf_list_prev(const pf_list_node_t* cur_node)
{
    assert(cur_node );

    return cur_node->prev;
}

int pf_list_push_front(pf_list_t* list, void* value)
{
    pf_list_node_t* new_list_node = NULL; 

    assert(list);
 
    new_list_node = malloc(sizeof(pf_list_node_t));
    if(!new_list_node)
    {
        pf_set_errno(PF_ENOMEM);
        return PF_ENOMEM;
    }
 
    new_list_node->data = value;
    new_list_node->next = list->head;
    new_list_node->prev = NULL;
 
    if(list->head)
    {
        list->head->prev = new_list_node;
    }
 
    list->head = new_list_node;
    list->size++;
 
    if(list->size == 1)
    {
        list->tail = list->head;
    }
 
    return 0;
}

int pf_list_push_back(pf_list_t* list, void* value)
{
    pf_list_node_t* new_list_node = NULL;

    assert(list);

    new_list_node = malloc(sizeof(pf_list_node_t));
    if(!new_list_node)
    {
        pf_set_errno(PF_ENOMEM);
        return PF_ENOMEM;
    }

    new_list_node->data = value;
    new_list_node->next = NULL;
    new_list_node->prev = list->tail;

    if(list->tail)
    {
        list->tail->next = new_list_node;
    }

    list->tail = new_list_node;
    list->size++;

    if(list->size == 1)
    {
        list->head = list->tail;
    }

    return 0;
}

void* pf_list_pop_front(pf_list_t* list)
{
    assert(list);

    return pf_list_erase(list,list->head);
}

void* pf_list_pop_back(pf_list_t* list)
{
    assert(list);

    return pf_list_erase(list,list->tail);
}

int pf_list_insert(pf_list_t* list, pf_list_node_t* node, void* value)
{
    pf_list_node_t* new_list_node = NULL;

    assert(list);

    if(list->size == 0)
    {
        return pf_list_push_back(list,value);
    }
    else if(list->size == UINT32_MAX)
    {
        pf_set_errno(PF_EDQUOT);       
        return PF_EDQUOT;    
    }

    assert(node);

    new_list_node = malloc(sizeof(pf_list_node_t));
    if(!new_list_node)
    {
        pf_set_errno(PF_ENOMEM);
        return PF_ENOMEM;
    }
    new_list_node->data = value;
    new_list_node->prev = node;


    new_list_node->next = node->next;
    if(node->next)
    {
        node->next->prev = new_list_node;
    }
    node->next = new_list_node;

    if(node == list->tail)
    {
        list->tail = new_list_node;
    }

    list->size++;

    return 0;
}

void* pf_list_erase(pf_list_t* list, pf_list_node_t* node)
{
    void* data = NULL;

    assert(list);

    if(!node)
    {
        return NULL;
    }

    if(node->prev)
    {
        node->prev->next = node->next;
    }
    if(node->next)
    {
        node->next->prev = node->prev;
    }

    list->size--;
    if(list->head == node)
    {
        list->head = list->head->next;
    }
    if(list->tail == node)
    {
        list->tail = list->tail->prev;
    }

    data = node->data;
    free(node);

    return data;
}

uint32_t pf_list_count(const pf_list_t* list)
{
    assert(list);

    return list->size;
}

int pf_list_clear(pf_list_t* list)
{
    pf_list_node_t* head = NULL;
    pf_list_node_t* next = NULL;

    assert(list);

    head = list->head;
    while(head)
    {
        next = head->next;
        free(head);
        head = next;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;

    return 0;
}

int32_t pf_list_for_each(const pf_list_t* list,
                         int forward,
                         void* arg,
                         int (*cb)(void* arg, pf_list_node_t* node))
{
    int ret             = 0;
    pf_list_node_t* pos = NULL;
    pf_list_node_t* cur = NULL;

    assert(list);
    assert(cb);

    if(forward)
    {
        pos = list->head;
        while(pos)
        {
            cur = pos;
            pos = cur->next;
            if((ret = (*cb)(arg, cur)) != 0)
            {
                return ret;
            }
        }
    }
    else
    {
        pos = list->tail;
        while(pos)
        {
            cur = pos;
            pos = cur->prev;
            if((ret = (*cb)(arg, cur)) != 0)
            {
                return ret;
            }
        }
    }

    return 0;
}

int pf_list_sort(pf_list_t* list,
                 int (*comp)(const void*, const void*))
{
    if(list == NULL || list->head == NULL)
    {
        return 0;
    }
    list->head = pf_list_sort_mine(list, list->head, comp);

    return 0;
}

int pf_list_qsort(pf_list_t* list,
                  int (*comp)(const void*, const void*))
{
    if(list == NULL)
    {
        return 0;
    }

    if(list->size <= 1)
    {
        return 0;
    }
    pf_list_quick_sort(list->head, list->tail, comp);

    return 0;
}

/********************************************************************************************/

static inline pf_list_node_t* pf_list_sort_merge(pf_list_t* list,
                                                 pf_list_node_t* l1,
                                                 pf_list_node_t* l2,
                                                 int (*compare_func)(const void*, const void*))
{
    pf_list_node_t node_list;
    pf_list_node_t* l = NULL;
    pf_list_node_t* lprev = NULL;
    pf_list_node_t* node_tmp = NULL;
    int cmp;

    l = &node_list;
    lprev = NULL;

    while(l1 && l2)
    {
        cmp = (compare_func)(l1->data, l2->data);

        if(cmp <= 0)
        {
            if(l1 == list->tail)
            {
                list->tail = l2;
            }

            l->next = l1;
            l1 = l1->next;
        }
        else
        {
            if(l2 == list->tail)
            {
                list->tail = l1;
            }

            l->next = l2;
            l2 = l2->next;
        }
        l = l->next;
        l->prev = lprev;
        lprev = l;
    }
    l->next = l1 ? l1 : l2;
    l->next->prev = l;

    node_tmp = l->next;
    if(node_tmp == list->tail)
    {
        while(node_tmp->next)
        {
            node_tmp = node_tmp->next;
        }
        list->tail = node_tmp;
    }

    return node_list.next;
}

static inline pf_list_node_t* pf_list_sort_mine(pf_list_t* list,
                                                pf_list_node_t* list_node,
                                                int (*comp)(const void*, const void*))
{
    pf_list_node_t* l1 = NULL;
    pf_list_node_t* l2 = NULL;

    if(!list_node->next)
    {
        return list_node;
    }

    l1 = list_node;
    l2 = list_node->next;

    while((l2 = l2->next) != NULL)
    {
        if((l2 = l2->next) == NULL)
        {
            break;
        }
        l1 = l1->next;
    }
    l2 = l1->next;
    l1->next = NULL;

    return pf_list_sort_merge(list, pf_list_sort_mine(list, list_node, comp), 
                              pf_list_sort_mine(list, l2, comp), comp);
}

static inline pf_list_node_t* pf_list_partion(pf_list_node_t* node_low, 
                                              pf_list_node_t* node_high,
                                              int (*comp)(const void*, const void*))
{
    void* tmp = NULL;
    void* pivot = NULL;

    pivot = node_low->data;
    while(node_low != node_high)
    {
        /* from back to front */
        while(node_low != node_high && comp(node_high->data, pivot) >= 0)
        {
            node_high = node_high->prev;
        }
        /* swap */
        tmp = node_low->data;
        node_low->data = node_high->data;
        node_high->data = tmp;

        /* from front to back */
        while(node_low != node_high && comp(node_low->data, pivot) <= 0)
        {
            node_low = node_low->next;
        }
        /* swap */
        tmp = node_low->data;
        node_low->data = node_high->data;
        node_high->data = tmp;
    }

    return node_low;
}

static inline void pf_list_quick_sort(pf_list_node_t* node_low, 
                                      pf_list_node_t* node_high,
                                      int (*comp)(const void*, const void*))
{
    pf_list_node_t* node_tmp = NULL;

    node_tmp = pf_list_partion(node_low, node_high, comp);
    if(node_low != node_tmp)
    {
        pf_list_quick_sort(node_low, node_tmp->prev, comp);
    }
    if(node_high != node_tmp)
    {
        pf_list_quick_sort(node_tmp->next, node_high, comp);
    }

    return;
}
